import java.util.*;

public class FindFrequentTreeSum {
    Map<Integer, Integer> map = new HashMap<>(); //大小 -> 次数
    int size = 0; //记录个数

    public int[] findFrequentTreeSum(TreeNode root) {
        treeSum(root);
        Set<Map.Entry<Integer, Integer>> set = map.entrySet();
        List<Integer> list = new ArrayList<> ();
        for (Map.Entry<Integer, Integer> entry : set) {
            if (entry.getValue() == size) {
                list.add(entry.getKey());
            }
        }
        int k = list.size();
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = list.get(i);
        }
        return ret;
    }

    private int treeSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftSum = treeSum(root.left);
        int rightSum = treeSum(root.right);
        int curTreeSum = leftSum + rightSum + root.val;
        hashShoot(curTreeSum);
        return curTreeSum;
    }

    private void hashShoot(int val) {
        map.put(val, map.getOrDefault(val, 0) + 1);
        size = Math.max(size, map.get(val));
    }
}
